package match

func patternLPS(pat []rune) []int {
	lps := make([]int, len(pat))
	for j, i := 0, 1; i < len(pat); {
		if pat[i] == pat[j] {
			lps[i] = j + 1
			i++
			j++
		} else {
			if j == 0 {
				lps[i] = 0
				i++
			} else {
				j = lps[j-1]
			}
		}
	}
	return lps
}

func kmp(txt, pat []rune) []int {
	n, m := len(txt), len(pat)
	lps := patternLPS(pat)
	result := []int{}
	for i, j := 0, 0; i < n; {
		if pat[j] == txt[i] {
			i++
			j++
		}
		if j == m {
			result = append(result, i-m) // matched
			j = lps[j-1]
		}
		if j < m && i < n && pat[j] != txt[i] {
			if j != 0 {
				j = lps[j-1]
			} else {
				i++
			}
		}
	}
	return result
}

// KMP string pattern matching KMP algorithm
func KMP(txt, pat string) []int {
	if len(pat) == 0 {
		return []int{}
	}
	return kmp([]rune(txt), []rune(pat))
}
